(1) Field of the Invention
The present invention relates in general to the detection of feature points in images, and more specifically to the detection of blobs. A blob is a particular type of feature point comprising a region in the image that has different intensity from the surrounding area.
(2) Description of Related Art
Blob detection has a large number of uses for example in optical motion capture and photogrammetry. In many such applications, it is desired to detect accurately the position of feature points in images. For example, in optical motion capture a fiducial or marker is applied to an object, such as a person. The fiducial forms a blob in an optical image of the object. The position of the blob in the image is detected.
A large number of blob detection techniques are known. Most of these known blob detection techniques detect regions where the contrast between foreground and background intensities are high.
A simple known technique for blob detection is thresholding. Blobs are detected by detecting regions of pixels exceeding a global contrast threshold. Thresholding is used in several commercial optical motion capture systems. Herein optical systems use retro-reflective spherical fiducials illuminated by stroboscopic lighting collocated with the camera lens. Under controlled conditions, this technology enables the images of the fiducials to appear much brighter than the background, especially compared to their appearance under ambient light. A threshold is then used to detect the fiducials having pixel-intensity values above the threshold. Since this thresholding scheme is very straightforward, the detection can be done on the cameras, typically on an FPGA (field-programmable gate array). Hence, only the fiducial centroids and radii have to be processed at a later stage to do motion capture analysis instead of the raw images. Due to this on-camera processing, these systems are typically very fast, operating in real-time.
These optical motion capture systems are, however, sensitive to variant lighting conditions and therefore not highly suitable for outdoors use. It would therefore be desirable to alleviate the strict requirements on the fiducials and illumination thereof. However, this reduces the contrast of the blobs in the image and therefore requires a more sensitive blob detection technique. In particular, simple thresholding cannot be applied as there will be many regions in the image having a similar intensity to the fiducials.
More sophisticated blob detection techniques are known, including template matching, and differential techniques. For example Shortis et al., “A comparison of some techniques for the subpixel location of discrete target images”, In Proceedings of the SPIE: Videometrics III, Vol. 2350, 1994, pp 239-250 discloses some of the earlier methods to do automatic target detections for the purposes of photogrammetry, such as thresholding, template matching, match filtering and least square ellipse fitting. The accuracy of the derived centroids is compared.
Template matching and matched filter techniques typically generate and use a set of templates describing the shape to detect and correlate the template with all the pixels in the images. Any general shape can then be detected where the correlation is above a predefined threshold. The template is usually a square image, for example an window of 11-by-11 pixels containing a circular shape. For very specific cases this approach works well, but for noisy shapes robust detection is only possible with a comprehensive set of templates to compensate for shape differences, sensor noise, background variations and so on. Increasing the number of templates increases the computation time significantly. This is a problem. For example Menze et al., “From eigenspots to fisherspots—latent spaces in the nonlinear detection of spot patterns in a highly varying background”, (2006) discloses compression of the templates to speed up the matching.
An example of a template matching technique is disclosed in Claus and Fitzgibbon, “Reliable fiducial detection in natural scenes”, Proceedings of the 8th European Conference on Computer Vision, Prague, Czech Republic, Vol. 3024, Springer-Verlag, 2004, pp 469-480 for detecting blobs as part of fiducial detection in natural scenes. Template matching is applied, wherein a nearest neighbour classifier is used to determine if a pattern is closer to a blob training example or an arbitrary background example.
There are also known differential blob detection techniques which use second derivatives to detect blobs. A comprehensive survey of techniques that fall into this category can be found in Mikolajczyk and Schmid, “A performance evaluation of local descriptors”, IEEE Transactions on Pattern Analysis & Machine Intelligence 27 (10) (2005), pp 1615-1630.
One differential technique is based on the Laplacian of Gaussian, for example as disclosed in Blostein and Ahuja, “A multiscale region detector”, Computer Vision, Graphics, and Image Processing 45 (1) (1989), pp 22-41.
Similar techniques are based on the determinant of the Hessian, after computing the gradient of the image, for example as disclosed in Hinz, “Fast and subpixel precise blob detection and attribution”, ICIP05, 2005, pp III: 457-460 and in Shneier, “Using pyramids to define local thresholds for blob detection, PAMI 5(3) (1983), pp 345-349. Such techniques mainly try to detect regions where the contrast is high. The detected regions are useful for some applications, but the accuracy of the detected position is generally low and not sufficient for applications such as optical motion capture and photogrammetry. Also, the detected blobs do not necessarily have a predefined shape such as a circle. Accordingly, the techniques may tend to generate false-positive detection where it is desired to detect a fiducial having a certain shape.
A related approach to feature point detection is arc segmentation which describes the process of detecting arcs in images, for example circles in engineering drawings. The edges in images are pivotal to these techniques. A useful literature study of known arc segmentation techniques is contained in Song et al., “Effective multiresolution arc segmentation: Algorithms and performance evaluation”, IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (8), 1994.
One type of arc segmentation technique uses the Hough transform to detect circles and lines in images. The Hough transform maps the image into a parameter space for the shape one wishes to detect. The set of parameter values which will cause an intersection of the parametric shape (e.g. line or circle) with an edge pixel are calculated. The process is repeated for each edge pixel, and the parameter values satisfying the edge pixels are thereby accumulated in the parameter space. This accumulation can be weighted according to the strength of the edge. The local maxima of the accumulated values in the parameter space then correspond to the parameters of the shape satisfying most edge pixels. Therefore, shapes can be matched and extracted from the edge pixel image by finding the local maxima in the Hough-transformed parameter space.
Although robust, arc segmentation techniques are generally very computationally expensive and therefore slow. Although the technique works well to detect lines, the degree of computation increases as the parameter space increases. For example, circles require a three-dimensional parameter space and ellipses a five-dimensional space. Furthermore, the parameter space must generally be discrete and bounded in order to compute the transform. Detecting more possible parameter variations requires finer re-sampling and wider bounds on parameter values. Thus in general terms, such arc segmentation techniques are not readily adaptable to blob detection at high speed.
Other feature point detection techniques use colour information present in images. For example, Murch and Chalup, “Combining edge detection and colour segmentation in the four-legged league”, Proceedings of the Australian Robotics and Automation Association, 2004 discloses combining edge detection and colour segmentation to detect balls in RGB images. A single ball is found according to the largest blob found with a specific colour. Whilst this can be a useful technique, it is limited to specific applications where an object has a distinctive colour. It is also limited by the colour models of the available cameras. Often colour information is provided at the expense of spatial information, but spatial information is vital to detect small blobs. Also, a global threshold is usually applied to do colour segmentation, so these techniques suffer from the problems with thresholding discussed above.
It would be desirable to develop blob detection techniques which alleviate at least some of these problems.